//==============================================================================
//
//      DBigInt - the arbitrary length integer number class in the ofc-library
//
//               Copyright (C) 2005  Dick van Oudheusden
//  
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this library; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2006-07-22 13:28:55 $ $Revision: 1.8 $
//
//==============================================================================

#include "ofc/DBigInt.h"

#ifdef HAVE_DBIGINT
#include <gmp.h>
#endif

#include <ctype.h>


#if _INTERFACE_

#include "ofc/config.h"

#include "ofc/DTextable.h"
#include "ofc/DDatable.h"
#include "ofc/DParsable.h"
#include "ofc/DSimpleArithmetic.h"
#include "ofc/DBitArithmetic.h"
#include "ofc/DComparable.h"
#include "ofc/DText.h"

#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H)
#define HAVE_DBIGINT  1
#endif

#ifdef HAVE_DBIGINT

//
// The big int class implements a number of methods for working with arbitrary large integer numbers.
// The class uses the excellent gmp library for the actual calculations.
// 

@interface DBigInt : Object <DTextable,DParsable,DDatable,DSimpleArithmetic,DBitArithmetic,DComparable>
{
@private
  void        *_value;      // the bit integer value
}

#endif
#endif



#ifdef HAVE_DBIGINT


@implementation DBigInt

#if _PRIVATE_

static BOOL _gmpInitialised = NO;

static void * _gmpRealloc(void *ptr, size_t old_size, size_t new_size)
{
  return objc_realloc(ptr, new_size);
}

static void _gmpFree(void *ptr, size_t old_size)
{
  objc_free(ptr);
}


void _gmpInit()
{
  if (!_gmpInitialised)
  {
    mp_set_memory_functions(objc_malloc, _gmpRealloc, _gmpFree);
    
    _gmpInitialised = YES;
  }
}


#endif


//// Constructors

//
// Initialise to integer zero
//
// @return the object
//

- (DBigInt *) init
{
  [super init];

  _gmpInit();
  
  _value = objc_malloc(sizeof(mpz_t));
  
  mpz_init((mpz_ptr) _value);
  
  return self;
}

//
// Initialise to a (small) number
//
// @param number   the (small) number
//
// @return the object
//

- (DBigInt *) init :(long) number
{
  [self init];

  [self set :number];

  return self;
}

//
// Initialise with a string
// 
// @param cstring  the cstring with the number
// @param base     the base for the number
// 
// @return the object
// 
- (DBigInt *) init :(const char *) cstring :(int) base
{
  [self init];
  
  [self set :cstring :base];
  
  return self;
}


//// Copy constructor

//
// Do a shallow copy of the object
//
// @return the object
//
- shallowCopy
{
  DBigInt *copy = [super shallowCopy];
  
  copy->_value  = objc_malloc(sizeof(mpz_t));
  
  mpz_init_set((mpz_ptr) copy->_value, _value);

  return copy;
}


//// Deconstructor

//
// Free a big integer
// 
// @return the object
//
- free
{
  mpz_clear((mpz_ptr) _value );
  
  objc_free(_value); _value = nil;
  
  return [super free];
}


// Member methods

//
// Check if the big integer is negative
// 
// @return is it?
// 
- (BOOL) isNegative
{
  return (mpz_sgn((mpz_ptr) _value) < 0);
}

//
// Check if the big integer is zero
// 
// @return is it ?
// 
- (BOOL) isZero
{
  return (mpz_sgn((mpz_ptr) _value) == 0);
}


//// Set methods

//
// Set the big integer to zero
// 
// @return the object
// 
- (DBigInt *) clear
{
  mpz_set_ui((mpz_ptr) _value, 0);

  return self;
}

//
// Set the big integer with a (small) number
//
// @param number   the (small) number
//
// @return the object
//
- (DBigInt *) set :(long) number
{
  mpz_set_si((mpz_ptr) _value, number);
  
  return self;
}

//
// Set the big integer with an array of bytes
//
// @param numbers   the number in an array of bytes [0] = least significant (NULL = number 0)
// @param length    the number of bytes in number (length 0 = number 0)
// @param negative  should the number be negative ?
//
// @return the object
//
- (DBigInt *) set :(const unsigned char *) number :(unsigned long) length :(BOOL) negative
{
  if ((length == 0) || (number == NULL))
  {
    [self clear];
  }
  else
  {
    mpz_import((mpz_ptr) _value, length, -1, sizeof(unsigned char), 0, 0, number);
    
    if (negative)
    {
      [self negate];
    }
  }

  return self;
}

//
// Set the big integer with a text number
//
// @param cstring   the cstring with the number
// @param base      the base of the number (2..36)
//
// @return success
//
- (BOOL) set :(const char *) cstring :(int) base
{
  BOOL ok = NO;
  
  if ((base < 2) || (base > 36))
  {
    WARNING(DW_INVALID_ARG, "base");
  }
  else
  {
    ok = (mpz_set_str((mpz_ptr) _value, cstring, base) != -1);
  }

  return ok;
}

//
//
// Move an other object in this object
//
// @param other    the other object
//
// @return this object
//
- (DBigInt *) move :(DBigInt *) other
{
  if (other == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "other");
  }
  else
  {
    mpz_set((mpz_ptr) _value, (mpz_ptr) other->_value);
  }
  
  return self;
}


//// Get methods

//
// Get the big integer as (small) integer
// 
// @return the (small) integer
// 
- (long) get
{
  return mpz_get_si((mpz_ptr) _value);
}

//
// Get the big integer as a text string
// 
// @param base     the base for the text string (2..36)
// 
// @return a (new) text string (or nil)
// 
- (DText *) get :(int) base
{
  DText *str = nil;
  
  if ((base < 2) || (base > 36))
  {
    WARNING(DW_INVALID_ARG, "base");
  }
  else
  {
    char *out = mpz_get_str(NULL, base, (mpz_ptr) _value);
    
    if (out != NULL)
    {
      str = [DText new];
      
      [str set :out];
      
      objc_free(out);
    }
  }
  
  return str;
}

//
// Return the big number as data string (note: keep the negative state seperate)
// 
// @return the number in a (new) data string (empty for number 0)
// 
- (DData *) toData
{
  DData *number = [DData new];
  
  unsigned char *data   = NULL;
  size_t         length = 0;
  
  data = mpz_export(NULL, &length, -1, sizeof(unsigned char), 0, 0, (mpz_ptr) _value);
  
  if (data != NULL)
  {
    [number set :data :length];
    
    objc_free(data);
  }
      
  return number;
}


//// Methods on big integer numbers

//
// Add with a big integer 
//
// @param other    the big integer
//
// @return the object
//
- (DBigInt *) add :(DBigInt *) other
{
  if (other == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "other");
  }
  else 
  {
    mpz_add((mpz_ptr) _value, (mpz_ptr) _value, (mpz_ptr) other->_value);
  }
  
  return self;
}

//
// Add two big integers and store the result in the object
//
// @param src1     the first big integer
// @param src2     the second big integer
//
// @return the object
//

- (DBigInt *) add :(DBigInt *) src1 :(DBigInt *) src2
{
  if ((src1 == nil) || (src2 == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "src?");
  }
  else 
  {
    mpz_add((mpz_ptr) _value, (mpz_ptr) src1->_value, (mpz_ptr) src2->_value);
  }
  
  return self;
}

//
// Subract with a big integer
//
// @param other     the big integer
//
// @return the object
//

- (DBigInt *) sub :(DBigInt *) other
{
  if (other == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "other");
  }
  else
  {
    mpz_sub((mpz_ptr) _value, (mpz_ptr) _value, (mpz_ptr) other->_value);
  }

  return self;
}

//
// Subract two big integers and store the result in the object
//
// @param src1      the first big integer
// @param src2      the second big integer
//
// @return the object
//

- (DBigInt *) sub :(DBigInt *) src1 :(DBigInt *) src2
{
  if ((src1 == nil) || (src2 == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "src?");
  }
  else
  {
    mpz_sub((mpz_ptr) _value, (mpz_ptr) src1->_value, (mpz_ptr) src2->_value);
  }

  return self;
}

//
// Multiply with a big integer
//
// @param other    the big integer
//
// @return the object
//

- (DBigInt *) mul :(DBigInt *) other
{ 
  if (other == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "other");
  }
  else
  {
    mpz_mul((mpz_ptr) _value, (mpz_ptr) _value, (mpz_ptr) other->_value);
  }
  
  return self;
}

//
// Multiply two big integers and store the result in the object
//
// @param src1    the first big integer
// @param src2    the second big integer
//
// @return the object
//

- (DBigInt *) mul :(DBigInt *) src1 :(DBigInt *) src2
{ 
  if ((src1 == nil) || (src2 == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "src?");
  }
  else
  {
    mpz_mul((mpz_ptr) _value, (mpz_ptr) src1->_value, (mpz_ptr) src2->_value);
  }
  
  return self;
}

//
// Divide with a big integer
//
// @param other    the divider
//
// @return the object
//

- (DBigInt *) div :(DBigInt *) other
{
  if (other == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "other");
  }
  else
  {
    mpz_fdiv_q((mpz_ptr) _value, (mpz_ptr) _value, (mpz_ptr) other->_value);
  }
  
  return self; 
}

//
// Divide two big integers and store the result in the object
//
// @param src1    the number
// @param src2    the divider
//
// @return the object
//

- (DBigInt *) div :(DBigInt *) src1 :(DBigInt *) src2
{
  if ((src1 == nil) || (src2 == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "src?");
  }
  else
  {
    mpz_fdiv_q((mpz_ptr) _value, (mpz_ptr) src1->_value, (mpz_ptr) src2->_value);
  }
  
  return self; 
}

//
// Determine the module with a big integer
//
// @param other    the divider
//
// @return the object
//

- (DBigInt *) mod :(DBigInt *) other 
{
  if (other == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "other");
  }
  else
  {
    mpz_fdiv_r((mpz_ptr) _value, (mpz_ptr) _value, (mpz_ptr) other->_value);
  }
  
  return self; 
}
//
// Determine the module from two big integers and store the result in the object
//
// @param src1     the number
// @param src2     the divider
//
// @return the object
//
- (DBigInt *) mod :(DBigInt *) src1 :(DBigInt *) src2
{
  if ((src1 == nil) || (src2 == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "src?");
  }
  else
  {
    mpz_fdiv_r((mpz_ptr) _value, (mpz_ptr) src1->_value, (mpz_ptr) src2->_value);
  }
  
  return self; 
}

//
// Absolute the big integer
// 
// @return the object
// 

- (DBigInt *) abs
{
  mpz_abs((mpz_ptr) _value, (mpz_ptr) _value);
  
  return self;
}

//
// One's complement the big integer
// 
// @return the object
// 
- (DBigInt *) com
{
  mpz_com((mpz_ptr) _value, (mpz_ptr) _value);
  
  return self;
}
 
//
// Negate the big integer
// 
// @return the object
// 
- (DBigInt *) negate
{
  mpz_neg((mpz_ptr) _value, (mpz_ptr) _value);
  
  return self;
}

//
// And with a big integer
// 
// @param other    the other big integer
// 
// @return the object
// 
- (DBigInt *) and :(DBigInt *) other
{
  if (other == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "other");
  }
  else
  {
    mpz_and((mpz_ptr) _value, (mpz_ptr) _value, (mpz_ptr) other->_value);
  }
  
  return self;
}

//
// And two big integers and store the result in the object
// 
// @param src1     the first big integer
// @param src2     the second big integer
// 
// @return the object
// 
- (DBigInt *) and :(DBigInt *) src1 :(DBigInt *) src2
{
  if ((src1 == nil) || (src2 == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "src?");
  }
  else
  {
    mpz_and((mpz_ptr) _value, (mpz_ptr) src1->_value, (mpz_ptr) src2->_value);
  }
  
  return self;
}

//
// Or with a big integer
// 
// @param other    the other big integer
// 
// @return the object
// 
- (DBigInt *) or :(DBigInt *) other
{
  if (other == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "other");
  }
  else
  {
    mpz_ior((mpz_ptr) _value, (mpz_ptr) _value, (mpz_ptr) other->_value);
  }
  
  return self;
}

//
// Or two big integers and store the result in the object
// 
// @param src1     the first big integer
// @param src2     the second big integer
// 
// @return the object
// 
- (DBigInt *) or :(DBigInt *) src1 :(DBigInt *) src2
{
  if ((src1 == nil) || (src2 == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "src?");
  }
  else
  {
    mpz_ior((mpz_ptr) _value, (mpz_ptr) src1->_value, (mpz_ptr) src2->_value);
  }
  
  return self;
}

//
// Xor with a big integer
// 
// @param other    the other big integer
// 
// @return the object
// 
- (DBigInt *) xor :(DBigInt *) other
{
  if (other == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "other");
  }
  else
  {
    mpz_xor((mpz_ptr) _value, (mpz_ptr) _value, (mpz_ptr) other->_value);
  }
  
  return self;
}
//
// Xor two big integers and store the result in the object
// 
// @param src1     the first big integer
// @param src2     the second big integer
// 
// @return the object
// 
- (DBigInt *) xor :(DBigInt *) src1 :(DBigInt *) src2
{
  if ((src1 == nil) || (src2 == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "src?");
  }
  else
  {
    mpz_xor((mpz_ptr) _value, (mpz_ptr) src1->_value, (mpz_ptr) src2->_value);
  }
  
  return self;
}

//
// Left shift the big integer
// 
// @param shifts   the number of shifts
// 
// @return the object
// 
- (DBigInt *) lshift :(unsigned long) shifts
{
  if (shifts > 0)
  {
    mpz_mul_2exp((mpz_ptr) _value, (mpz_ptr) _value, shifts);
  }
  
  return self;
}

//
// Left shift a big integer and store the result in the object
//
// @param src      the number to be shifted
// @param shifts   the number of shifts
// 
// @return the object
// 
- (DBigInt *) lshift :(DBigInt *) src :(unsigned long) shifts
{
  if (shifts > 0)
  {
    mpz_mul_2exp((mpz_ptr) _value, (mpz_ptr) src->_value, shifts);
  }
  
  return self;
}

//
// Right shift the big integer
// 
// @param shifts   the number of shifts
// 
// @return the object
// 
- (DBigInt *) rshift :(unsigned long) shifts
{
  if (shifts > 0)
  {
    mpz_fdiv_q_2exp((mpz_ptr) _value, (mpz_ptr) _value, shifts);
  }

  return self;
}

//
// Right shift a big integer and store the big integer
// 
// @param src      the number to be shifted
// @param shifts   the number of shifts
// 
// @return the object
// 
- (DBigInt *) rshift :(DBigInt *) src :(unsigned long) shifts
{
  if (shifts > 0)
  {
    mpz_fdiv_q_2exp((mpz_ptr) _value, (mpz_ptr) src->_value, shifts);
  }

  return self;
}


//// DComparable protocol implementation

//
// Compare with a big integer
//
// @param other    the other big integer
// 
// @return the compare result (-1,0,1)
//

- (int) compare :(DBigInt *) other
{
  int result = 0;
  
  if (other == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "other");
  }
  else
  {
    result = mpz_cmp((mpz_ptr) _value, (mpz_ptr) other->_value);
  }
  
  return result;
}


//// Textable protocol implementation

//
// Convert to a decimal text string
//
// @return a (new) text string with the big integer (or nil)
//

- (DText *) toText
{
  return [self get :10];
}


//// DParsable protocol implementation

#if _PRIVATE_
//
// Check for octal number
//
// @param ch     the character
// 
// @return is it an octal number ?
//
static BOOL _isoct(char ch)
{
  return ((ch >= '0') && (ch <= '7'));
}
#endif

//
// Parse a string for a big integer. Formats:
// decimal:     [space]*[+-][1..9][0..9]*
// hexadecimal: [space]*[+-]0x[0..9a..f]*
// octal:       [space]*[+-]0[0..7]*
// 
// @param cstr     the string to be parsed (moved to the first non-parsable char)
// 
// @return the result (0,ERANGE,ENODATA)
// 
- (int) fromString :(char **) cstr
{
  DText *str    = [DText new];
  char  *pntr   = *cstr;
  char  *start  = pntr;
  int    result = ENODATA;
  BOOL   hex    = NO;
  BOOL   dec    = NO;
  BOOL   oct    = NO;
  
  while (isspace(*pntr)) // skip spaces
  {
    pntr++;
  }

  start = pntr;

  if ((*pntr == '+') || (*pntr == '-')) // process sign
  {
    [str push :*pntr++];
  }
  
  if (*pntr == '0') // process base indicator
  {
    [str push :*pntr++];
    
    if (tolower(*pntr) == 'x')
    {
      [str push :*pntr++];
      
      hex = YES;
    }
    else
    {
      oct = YES;
    }
  }
  else if (isdigit(*pntr))
  {
    dec = YES;
  }
  
  while ( ((isxdigit(*pntr)) && (hex)) || // scan the number
          ((isdigit (*pntr)) && (dec)) ||
          ((_isoct  (*pntr)) && (oct)) )
  {
    [str push :*pntr++];
  }
  
  if (pntr != start)
  {
    if (mpz_set_str((mpz_ptr) _value, [str cstring], 0) != -1)
    {
      result = 0;
      
      *cstr = pntr;
    }
    else
    {
      result = ERANGE;
    }
  }
  
  [str free];
  
  return result;
}

@end

#endif
  
/*===========================================================================*/

